package main

func isValid(s string) bool {
	size := 0
	for _, c := range s {
		switch c {
		case '(':
			size++
		case ')':
			if size == 0 {
				return false
			}
			size--
		}
	}
	return size == 0
}

var result []string

func generateParenthesis(n int) []string {
	result = nil
	doSearch("", n)
	return result
}

func doSearch(s string, n int) {
	if len(s) == 2*n { // reach limit
		if isValid(s) {
			result = append(result, s)
		}
	} else {
		doSearch(s+"(", n)
		doSearch(s+")", n)
	}
}

func main() {
	//println(isValid("(())"))
	//println(isValid("()()"))
	//println(isValid("())"))
	//println(isValid("(()"))
	re := generateParenthesis(0)
	println(re)
}
